package com.leetcode.周赛.第87场;

/**
 * @author: xiaomi
 * @date: 2021/1/22
 * @description: 844. 比较含退格的字符串
 * https://leetcode-cn.com/problems/backspace-string-compare/
 * 87场
 * https://leetcode-cn.com/contest/weekly-contest-87/
 */
public class A_844_比较含退格的字符串 {


	public static void main(String[] args) {
		String s = "ab##";
		s = "ab#c";
		s = "bxj##tw";
		s = "bbbextm";
//		s = "xywrrmp";
//		s = "nzp#o#g";
		String t = "c#d#";
		t = "ad#c";
		t = "bxj###tw";
		t = "bbb#extm";
//		t = "xywrrmu#p";
//		t = "b#nzp#o#g";
		A_844_比较含退格的字符串 action = new A_844_比较含退格的字符串();
		boolean res = action.backspaceCompare(s, t);
		System.out.println("res = " + res);
	}

	/**
	 * 使用两个指针进行判断
	 * "ab##"
	 * "c#d#"
	 * --
	 * 1.就像投票，当出现 '#' 就 -1，其他就 +1 当 value == 1 时就可以进行比较
	 * --
	 * 虽然使用双指针判断比较麻烦，但是效率是毋庸置疑的。
	 * @param S
	 * @param T
	 * @return
	 */
	public boolean backspaceCompare(String S, String T) {
		int index1 = S.length();
		int index2 = T.length();
		int value1 = 0, value2 = 0;
		char c1, c2;
		while (index1 > 0 && index2 > 0) {

			while (index1 > 0 && value1 < 1) {
				index1--;
				if (S.charAt(index1) == '#') {
					value1--;
				} else {
					value1++;
				}
			}
			if (index1 == 0 && value1 < 1) {
				c1 = ' ';
			} else {
				c1 = S.charAt(index1);
			}

			while (index2 > 0 && value2 < 1) {
				index2--;
				if (T.charAt(index2) == '#') {
					value2--;
				} else {
					value2++;
				}
			}
			if (index2 == 0 && value2 < 1) {
				c2 = ' ';
			} else {
				c2 = T.charAt(index2);
			}


			if (c1 != c2) {
				return false;
			}
			value1 = 0;
			value2 = 0;
		}
		//对于没有处理完的数据，需要继续判断
		if (index1 > 0) {
			//说明 index2 已经处理完 index2 = 0
			while (index1 > 0 && value1 < 1) {
				index1--;
				if (S.charAt(index1) == '#') {
					value1--;
				} else {
					value1++;
				}
			}
			if (index1 == 0 && value1 < 1) {
				return true;
			} else {
				return false;
			}
		} else if (index2 > 0) {
			while (index2 > 0 && value2 < 1) {
				index2--;
				if (T.charAt(index2) == '#') {
					value2--;
				} else {
					value2++;
				}
			}
			if (index2 == 0 && value2 < 1) {
				return true;
			} else {
				return false;
			}
		}

		return true;
	}


}
